//
//  912. 排序数组(手撕快速排序).swift
//  Top600
//
//  Created by rjb on 2021/8/4.
//
import Foundation
// 这个在leetcode里Swift会超时。
class Solution912 {
    func sortArray(_ nums: [Int]) -> [Int] {
        var nums = nums
        quickPart(nums: &nums, start: 0, end: nums.count - 1)
        return nums
    }
    func quickPart(nums: inout [Int], start: Int, end: Int) {
        if end <= start {
            return
        }
        let mid = partion(a: &nums, start, end: end)
        quickPart(nums: &nums, start: start, end: mid - 1)
        quickPart(nums: &nums, start: mid + 1, end: end)
    }
    // 将一个区间分割成两段，并返回中间的index
    // 其中一种简单的方法：找出小于pivot的个数。
    func partion(a: inout [Int], _ start: Int , end: Int) -> Int{
        let pivot = end
        var counter = start
        for i in start..<end {
            // 如果当前的值小于基准值。就将a[i]的元素放到a[counter]里
            if a[i] < a[pivot] {
               let temp = a[counter]
                a[counter] = a[i]
                a[i] = temp
                counter += 1
            }
        }
        // 最后将a[pivot]的值与a[counter]位置交换
        let tmp = a[pivot]
        a[pivot] = a[counter]
        a[counter] = tmp
        return counter
    }
    static func test() {
        let solution = Solution912()
        let nums = [5,2,3,1]
        let result = solution.sortArray(nums)
        print(result)
    }
}
